package com.carl.leetcode.dp;

/**
 * Created by carlXie on 2016/1/6.
 * email: kkrimen@gmail.com
 */
public class DPClassicDemo {
    public static void main(String[] args) {
        maxSumOfSubsequence(new int[]{-2, 11, -4, 13, -5, -2});
    }

    /**
     * transfer equation: max[i] = max(sum[i], max[i - 1])
     * @param nums
     */
    public static void maxSumOfSubsequence(int[] nums) {
        int sum = 0, max = 0;
        for (int i = 0; i < nums.length ; i++) {
            sum += nums[i];
            if(sum > max)
                max = sum;
            if(sum < 0)
                sum = 0;
        }

        System.out.println("max sum: " + max);
    }
}
